// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import "fmt"

// MaxHeap表示一个最大堆数据结构
type MaxHeap struct {
	heapArray []int // 保存堆元素的切片
	size      int   // 堆的当前大小
	maxsize   int   // 堆的最大大小
}

// newMaxHeap 创建并返回一个新的 MaxHeap 对象
func newMaxHeap(maxsize int) *MaxHeap {
	MaxHeap := &MaxHeap{
		heapArray: []int{},
		size:      0,
		maxsize:   maxsize,
	}
	return MaxHeap
}

// 如果节点是叶节点，则 leaf 返回 true
func (m *MaxHeap) leaf(index int) bool {
	if index >= (m.size/2) && index <= m.size {
		return true
	}
	return false
}

// parent 返回给定节点的父节点
func (m *MaxHeap) parent(index int) int {
	return (index - 1) / 2
}

// leftChild 返回给定节点的左子节点
func (m MaxHeap) leftChild(index int) int {
	return 2*index + 1
}

// rightChild 返回给定节点的右孩子
func (m MaxHeap) rightChild(index int) int {
	return 2*index + 2
}

// insert 向堆中添加一个元素
func (m *MaxHeap) insert(item int) error {
	if m.size >= m.maxsize {
		return fmt.Errorf("Heap is full")
	}
	m.heapArray = append(m.heapArray, item) // 将新元素添加到切片的末尾
	m.size++
	m.upHeapify(m.size - 1) // 通过向上堆化新添加的元素来维护堆属性
	return nil
}

// swap 交换堆中两个元素的位置
func (m *MaxHeap) swap(first, second int) {
	temp := m.heapArray[first]
	m.heapArray[first] = m.heapArray[second]
	m.heapArray[second] = temp
}

// upHeapify 在插入元素后使用，如果元素大于其父元素，则通过与其父元素交换元素来维护堆属性
func (m *MaxHeap) upHeapify(index int) {
	for m.heapArray[index] > m.heapArray[m.parent(index)] {
		m.swap(index, m.parent(index))
		index = m.parent(index)
	}
}

// downHeapify 在删除元素后使用，如果元素小于其一个或两个子元素，则通过将元素与其较大的子元素交换来维护堆属性
func (m *MaxHeap) downHeapify(current int) {
	if m.leaf(current) {
		return
	}
	largest := current
	leftChildIndex := m.leftChild(current)
	rightRightIndex := m.rightChild(current)

	if leftChildIndex < m.size && m.heapArray[leftChildIndex] > m.heapArray[largest] {
		largest = leftChildIndex
	}
	if rightRightIndex < m.size && m.heapArray[rightRightIndex] > m.heapArray[largest] {
		largest = rightRightIndex
	}
	if largest != current {
		m.swap(current, largest)
		m.downHeapify(largest)
	}
	return
}

// buildMaxHeap 在 O(n) 时间内从无序切片构建堆
func (m *MaxHeap) buildMaxHeap() {
	for index := ((m.size / 2) - 1); index >= 0; index-- {
		m.downHeapify(index)
	}
}

// remove 从堆中移除最大元素（根节点）并返回
func (m *MaxHeap) remove() int {
	top := m.heapArray[0]
	m.heapArray[0] = m.heapArray[m.size-1]
	m.heapArray = m.heapArray[:(m.size)-1]
	m.size--
	m.downHeapify(0)
	return top
}

func main() {
	inputArray := []int{1, 6, 8, 9, 66, 88}
	maxHeap := newMaxHeap(len(inputArray))
	for i := 0; i < len(inputArray); i++ {
		maxHeap.insert(inputArray[i])
	}
	maxHeap.buildMaxHeap()
	fmt.Println("The Max Heap is ")
	for i := 0; i < len(inputArray); i++ {
		fmt.Println(maxHeap.remove())
	}
}

//$ go run maxHeap.go
//The Max Heap is
//88
//66
//9
//8
//6
//1
